package com.leetcode.algorithm.y22.m07.w2;

import java.util.HashMap;
import java.util.Map;

/**
 * 138. 复制带随机指针的链表
 * 
 * https://leetcode.cn/problems/copy-list-with-random-pointer/
 * 
 * @author jie.deng
 *
 */
public class Question0138Solution01 {

	public Node copyRandomList(Node head) {
		Node cur = head;
		Node sentinel = new Node(0);
		Node curNew = sentinel;
		Map<Node, Node> map = new HashMap<>();
		while (cur != null) {
			curNew.next = new Node(cur.val);
			curNew = curNew.next;
			curNew.random = cur.random;
			map.put(cur, curNew);
			cur = cur.next;
		}
		cur = sentinel;
		while (cur != null) {
			if (cur.random != null) {
				cur.random = map.get(cur.random);
			}
			cur = cur.next;
		}
		return sentinel.next;
	}

	class Node {
		int val;
		Node next;
		Node random;

		public Node(int val) {
			this.val = val;
			this.next = null;
			this.random = null;
		}

		public Node(int val, Node next) {
			this.val = val;
			this.next = next;
			this.random = null;
		}
	}
	
}
